// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include "windows.h"
//
// typedef int DataType;
//
// typedef struct TreeNode {
//     DataType value;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
//
// // 创建新节点
// TreeNode* CreateNode(DataType value) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) {
//         perror("Memory allocation failed");
//         exit(EXIT_FAILURE);
//     }
//     newNode->value = value;
//     newNode->left = newNode->right = NULL;
//     return newNode;
// }
//
// // 插入节点（二叉搜索树规则）
// TreeNode* InsertNode(TreeNode* root, DataType x) {
//     if (root == NULL) {
//         return CreateNode(x);
//     }
//     if (x < root->value) {
//         root->left = InsertNode(root->left, x);
//     } else {
//         root->right = InsertNode(root->right, x);
//     }
//     return root;
// }
//
// // 先序遍历
// void PreOrder(TreeNode* root) {
//     if(root) {
//         printf("%d ",root->value);
//         PreOrder(root->left);
//         PreOrder(root->right);
//     }
// }
//
// // 释放内存
// void FreeTree(TreeNode* root) {
//     if (root) {
//         FreeTree(root->left);
//         FreeTree(root->right);
//         free(root);
//     }
// }
//
// // 查找值为val的节点
// TreeNode* FindNode(TreeNode* root, DataType val) {
//     if (root == NULL) return NULL;
//     if (root->value == val) return root;
//
//     TreeNode* left = FindNode(root->left, val);
//     if (left != NULL) return left;
//
//     return FindNode(root->right, val);
// }
//
// // 找到p和q的最近公共祖先
// //实现思路
// // 查找节点功能：首先需要实现一个查找节点的函数，用于找到特定值的节点。
// // LCA算法：使用递归方法查找两个节点的最近公共祖先：
// // 如果当前节点是NULL，返回NULL
// // 如果当前节点是p或q，返回当前节点
// // 递归查找左右子树
// // 如果左右子树都找到节点，当前节点就是LCA
// // 否则返回非空的那个子树结果
// TreeNode *LowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//     if (root == NULL) return NULL;
//     if (root == p || root == q) return root;
//
//     TreeNode* left = LowestCommonAncestor(root->left, p, q);
//     TreeNode* right = LowestCommonAncestor(root->right, p, q);
//
//     if (left && right) return root;
//     return left ? left : right;
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root = NULL;
//     int values[] = {50, 30, 70, 20, 40, 60, 80};
//     int length = sizeof(values) / sizeof(values[0]);
//
//     // 构建二叉搜索树
//     for (int i = 0; i < length; i++) {
//         root = InsertNode(root, values[i]);
//     }
//
//     printf("先序遍历结果: ");
//     PreOrder(root);
//     printf("\n");
//
//     // 测试查找LCA
//     TreeNode* p = FindNode(root, 20);
//     TreeNode* q = FindNode(root, 40);
//
//     if (p && q) {
//         TreeNode* lca = LowestCommonAncestor(root, p, q);
//         printf("%d和%d的最近公共祖先是: %d\n", p->value, q->value, lca->value);
//     } else {
//         printf("未找到指定节点\n");
//     }
//
//     FreeTree(root);
//     return 0;
// }